/**
 * @file doublelinklist.cpp
 * @author Hu Yumeng (3210103435@zju.edu.cn)
 * @brief
 * @version 0.1
 * @date 2022-10-06
 *
 * @copyright Copyright (c) 2022
 *
 */
#ifndef DoubleLinkedList_H
#define DoubleLinkedList_H

/// @brief 创建模板
/// @tparam DT
template <typename DT>

class DoubleLinkedList
{
private:
	/**
	 * @class 定义节点类
	 *
	 */
	struct Node

	{
		/// @brief 节点数据.
		DT data;

		/// @brief 节点前向指针.
		Node *prev;

		/// @brief 节点后向指针.
		Node *next;

		/**
		 * @brief 节点的构造函数.
		 *
		 * @param d 初始化节点数据.
		 * @param p 初始化前向指针.
		 * @param n 初始化后向指针.
		 */
		Node(const DT &d = DT{}, Node *p = nullptr, Node *n = nullptr) : data{d}, prev{p}, next{n} {}

		/**
		 * @brief 节点的移动构造函数.
		 *
		 * @param d 初始化节点数据.
		 * @param p 初始化前向指针.
		 * @param n 初始化后向指针.
		 */
		Node(DT &&d, Node *p = nullptr, Node *n = nullptr) : data{std::move(d)}, prev{p}, next{n} {}
	};

public:
	/**
	 * @class const_iterator迭代器类，遍历链表，访问元素，但不能改变元素值
	 *
	 */
	class const_iterator
	{
	public:
	/**
	 * @brief const_iterator迭代器类默认无参构造函数
	 * 
	 */
		const_iterator() : current{nullptr}
		{
		}
		/**
		 * @brief 重载解引用符*
		 * 
		 * @return 当前节点数据的引用
		 */
	    const DT &operator*() const
		{
			return retrieve();
		}
		/**
		 * @brief 重载前缀自加运算++
		 *
		 * @return 后移一位的迭代器的引用
		 */
		const_iterator &operator++()
		{
			current = current->next;

			return *this;
		}
        /**
         * @brief 重载后缀自加运算++
         * 
         * @return 迭代器对象
         */
		const_iterator operator++(int)
		{
			const_iterator old = *this;

			++(*this);

			return old;
		}
		/**
		 * @brief 重载前缀自减运算--
		 *
		 * @return 前移一位的迭代器的引用
		 */
		const_iterator &operator--()
		{
			current = current->prev;

			return *this;
		}
		        /**
         * @brief 重载后缀自减运算--
         * 
         * @return 迭代器对象
         */
		const_iterator operator--(int)
		{
			const_iterator old = *this;

			--(*this);

			return old;
		}
		/**
		 * @brief 重载关系运算符==
		 * 
		 * @param rhs 迭代器的引用
		 * @return true 当迭代器的指针指向的节点相同时
		 * @return false 当迭代器的指针指向的节点不同时
		 */
		bool operator==(const const_iterator &rhs) const
		{
			return current == rhs.current;
		}
		/**
		 * @brief 重载关系运算符！=
		 * 
		 * @param rhs 迭代器的引用
		 * @return true 当迭代器的指针指向的节点不同时
		 * @return false 当迭代器的指针指向的节点相同时
		 */
		bool operator!=(const const_iterator &rhs) const
		{
			return !(*this == rhs);
		}

	protected:
		/// @brief 定义节点指针
		Node *current;
		/**
		 * @brief 读取指针指向节点的数据
		 * 
		 * @return 节点数据
		 */
		DT &retrieve() const
		{
			return current->data;
		}
        /**
         * @brief 有参构造函数
         * @param p 节点指针
         */
		const_iterator(Node *p) : current{p}
		{
		}
		/**
		 * @brief 友元，可访问私有区域
		 * 
		 */
		friend class DoubleLinkedList<DT>;
	};

	/**
	 * @class iterator类继承const_iterator，遍历链表，访问元素，可改
	 * 
	 */
	class iterator : public const_iterator
	{
	public:
		/**
		 * @brief 默认构造函数
		 * 
		 */
		iterator()
		{
		}
		/**
		 * @brief 重载解引用符*
		 * 
		 * @return 当前节点数据的引用
		 */
		DT &operator*()
		{
			return const_iterator::retrieve();
		}
		/**
		 * @brief 重载解引用符*
		 * 
		 * @return 当前节点数据的引用
		 */
		const DT &operator*() const
		{
			return const_iterator::operator*();
		}
		/**
		 * @brief 重载前缀自加运算++
		 *
		 * @return 后移一位的迭代器的引用
		 */
		iterator &operator++()
		{
			this->current = this->current->next;

			return *this;
		}
		/**
		 * @brief 重载后缀自加运算++
		 *
		 * @return 当前迭代器对象
		 */
		iterator operator++(int)
		{
			iterator old = *this;

			++(*this);

			return old;
		}
		/**
		 * @brief 重载前缀自减运算符--
		 *
		 * @return 前移一位的迭代器的引用
		 */
		iterator &operator--()
		{
			this->current = this->current->prev;

			return *this;
		}
		/**
		 * @brief 重载后缀自减运算--
		 *
		 * @return 当前迭代器对象
		 */
		iterator operator--(int)
		{

			iterator old = *this;

			--(*this);

			return old;
		}

	protected:
		/**
		 * @brief 构造函数
		 * 
		 * @param p 
		 */
		iterator(Node *p) : const_iterator{p}
		{
		}
		/**
		 * @brief 友元
		 * 
		 */
		friend class DoubleLinkedList<DT>;
	};

public:
	/**
	 * @brief 构造函数
	 * 
	 */
	DoubleLinkedList()
	{
		/**
		 * @brief 初始化函数
		 * 
		 */
		init();
	}
	/**
	 * @brief 析构函数
	 * 
	 */
	~DoubleLinkedList()
	{
		clear();
		delete head;
		delete tail;
	}
	/**
	 * @brief 拷贝构造函数
	 * 
	 * @param rhs 
	 */
	DoubleLinkedList(const DoubleLinkedList &rhs)
	{
		init();
		for (auto &x : rhs)

			push_back(x);
	}
	/**
	 * @brief 重载赋值运算符=
	 * 
	 * @param rhs 不可修改的DoubleLinkedList对象引用
	 * @return DoubleLinkedList& 
	 */
	DoubleLinkedList &operator=(const DoubleLinkedList &rhs)
	{
		DoubleLinkedList copy = rhs;
		std::swap(*this, copy);
		return *this;
	}
	/**
	 * @brief 移动构造函数
	 * 
	 * @param rhs 
	 */
	DoubleLinkedList(DoubleLinkedList &&rhs): theSize{rhs.theSize}, head{rhs.head}, tail{rhs.tail}
	{
		rhs.theSize = 0;

		rhs.head = nullptr;

		rhs.tail = nullptr;
	}
	/**
	 * @brief 重载赋值运算符=
	 * 
	 * @param rhs 右值引用
	 * @return DoubleLinkedList& 
	 */
	DoubleLinkedList &operator=(DoubleLinkedList &&rhs)
	{
		std::swap(theSize, rhs.theSize);

		std::swap(head, rhs.head);

		std::swap(tail, rhs.tail);

		return *this;
	}
	/**
	 * @brief 返回头节点对应的迭代器
	 * 
	 * @return iterator 
	 */
	iterator begin()
	{
		return {head->next};
	}
	/**
	 * @brief 返回头节点对应的迭代器
	 * 
	 * @return const_iterator 
	 */
	const_iterator begin() const
	{
		return {head->next};
	}
	/**
	 * @brief 返回尾节点对应的迭代器
	 * 
	 * @return iterator 
	 */
	iterator end()
	{
		return {tail};
	}
	/**
	 * @brief 返回尾节点对应的迭代器
	 * 
	 * @return const_iterator 
	 */
	const_iterator end() const
	{
		return {tail};
	}
	/**
	 * @brief 返回双链表长度
	 * 
	 * @return int 
	 */
	int size() const
	{
		return theSize;
	}
	/**
	 * @brief 判断双链表是否为空
	 * 
	 * @return true 为空
	 * @return false 不为空
	 */
	bool empty() const
	{
		return size() == 0;
	}
	/**
	 * @brief 清空链表
	 * 
	 */
	void clear()
	{
		while (!empty())

			pop_front();
	}
	/**
	 * @brief 返回头节点的数据
	 * 
	 * @return DT& 
	 */
	DT &front()
	{
		return *begin();
	}
	/**
	 * @brief 返回头节点的数据
	 * 
	 * @return const DT& 
	 */
	const DT &front() const
	{
		return *begin();
	}
	/**
	 * @brief 返回尾节点的数据
	 * 
	 * @return DT& 
	 */
	DT &back()
	{
		return *--end();
	}
	/**
	 * @brief 
	 * 
	 * @return const DT& 
	 */
	const DT &back() const
	{
		return *--end();
	}
	/**
	 * @brief 从头插入节点
	 * 
	 * @param x
	 */
	void push_front(const DT &x)
	{
		insert(begin(), x);
	}
	/**
	 * @brief 从头插入节点
	 * 
	 * @param x 右值
	 */
	void push_front(DT &&x)
	{
		insert(begin(), std::move(x));
	}
	/**
	 * @brief 在尾部插入节点
	 * 
	 * @param x 
	 */
	void push_back(const DT &x)
	{
		insert(end(), x);
	}
	/**
	 * @brief 在尾部插入节点
	 * 
	 * @param x 右值
	 */
	void push_back(DT &&x)
	{
		insert(end(), std::move(x));
	}
	/**
	 * @brief 移除头节点
	 * 
	 */
	void pop_front()
	{
		erase(begin());
	}
	/**
	 * @brief 移除尾节点
	 * 
	 */
	void pop_back()
	{
		erase(--end());
	}
	/**
	 * @brief 在itr迭代器指向位置前插x
	 * 
	 * @param itr 
	 * @param x 
	 * @return iterator 
	 */
	iterator insert(iterator itr, const DT &x)
	{
		Node *p = itr.current;

		theSize++;

		return {p->prev = p->prev->next = new Node{x, p->prev, p}};
	}
	/**
	 * @brief 在itr迭代器指向位置前插x
	 * 
	 * @param itr 
	 * @param x 右值
	 * @return iterator 
	 */
	iterator insert(iterator itr, DT &&x)
	{
		Node *p = itr.current;
		theSize++;
		return {p->prev = p->prev->next= new Node{std::move(x), p->prev, p}};
	}
	/**
	 * @brief 删除itr指向的节点
	 * 
	 * @param itr 
	 * @return iterator 删除节点后的节点迭代器
	 */
	iterator erase(iterator itr)
	{
		Node *p = itr.current;
		iterator retVal{p->next};
		p->prev->next = p->next;
		p->next->prev = p->prev;
		delete p;
		theSize--;
		return retVal;
	}
	/**
	 * @brief 删除[from， to]区间的数据，返回最后一个删除点之后的节点迭代器
	 * 
	 * @param from 
	 * @param to 
	 * @return iterator 
	 */
	iterator erase(iterator from, iterator to)
	{
		for (iterator itr = from; itr != to;)

			itr = erase(itr);

		return to;
	}

private:
	/// @brief 链表长度
	int theSize;

	/// @brief 头节点指针
	Node *head;

	/// @brief 尾节点指针
	Node *tail;

	/**
	 * @brief 
	 * 
	 */
	void init()
	{

		theSize = 0;

		head = new Node;

		tail = new Node;

		head->next = tail;

		tail->prev = head;
	}
};

#endif